package HMM;

import java.util.ArrayList;


/**
 * @author Gergely Neu
 *
 * Common static methods used by HMM and TrainingMethod classes.
 */
public class HMMCommonFunctions {
	 
		protected static DoubleSparseMatrix _viterbiScores;
		
		protected static IntSparseMatrix _bestPointer;
		
		/**
		 * Computes the Viterbi scores for a given emission array and a given HMM. 
		 * 
		 * _viterbiScores[i][s] = maximal score of decoding ending with state s at position i
		 * 
		 * @param emissionArray the given emissions. 
		 * @param emissionMx the emission matrix of the given HMM.
		 * @param transitionMx the transition matrix of the given HMM.
		 */
		public static void computeViterbiScores(int[] emissionArray, DoubleSparseMatrix emissionMx, DoubleSparseMatrix transitionMx){
			// initialization
			int i = 0;
			int L = emissionArray.length;
//			int numEmissions = emissionMx.getColNr();
			int numStates = transitionMx.getColNr();
			
			_viterbiScores = new DoubleSparseMatrix(numStates, L);
			
			_bestPointer = new IntSparseMatrix(numStates, L);
			
			for (int l = 0; l < numStates; l++)
				_viterbiScores.set(l,0, 0.0);
			
			for (i = 1; i < L; i++) { // sweep through words in the sentence
				for (int l : emissionMx.getPrecedingStates(emissionArray[i])) { // sweep through possible emitters
					DoubleSparseMatrix preScores = new DoubleSparseMatrix(numStates, 1);
					for (int k : transitionMx.getPrecedingStates(l)) // sweep through possible preceding states
						preScores.set(k, 0, _viterbiScores.get(k,i-1) + transitionMx.get(k,l));
					
					if (!transitionMx.getPrecedingStates(l).isEmpty()) {
						_bestPointer.set(l, i, argmax(preScores, transitionMx.getPrecedingStates(l), 0));
						_viterbiScores.set(l, i, emissionMx.get(l, emissionArray[i]) + preScores.get(_bestPointer.get(l,i), 0));}
					}
				
				 if (emissionMx.getPrecedingStates(emissionArray[i]).isEmpty()) {
					 for (int l = 0; l<numStates; l++) {
						 DoubleSparseMatrix preScores = new DoubleSparseMatrix(numStates, 1);
						 for (int k : transitionMx.getPrecedingStates(l)) // sweep through possible preceding states
								preScores.set(k, 0, _viterbiScores.get(k,i-1) + transitionMx.get(k,l));
						 _bestPointer.set(l, i, argmax(preScores, transitionMx.getPrecedingStates(l), 0));
						_viterbiScores.set(l, i, preScores.get(_bestPointer.get(l,i), 0));
					 }
				 }
			}
		}
		
		public static double getViterbiScores(int rootIndex, int rootState) {
			return _viterbiScores.get(rootState, rootIndex);
		}
		
		/**
		 * Returns the maximum scoring state array spanning over emissions ranging from emissionArray[0] to emissionArray[rootIndex-1].
		 * The last state in the array is forced to be rootState.
		 * 
		 * @param emissionArray the emissions to decode.
		 * @param rootIndex the length of the decoded state sequence.
		 * @param rootState the last state.
		 * @return the array of states described above.
		 */
		public static int[] decodeFrom(int[] emissionArray, int rootIndex, int rootState){
			int L = emissionArray.length;
			if (rootIndex>=L) {
				rootIndex = L;
				rootState = 0;
			}
			int currentState = rootState;
			int[] stateArray = new int[rootIndex];
			
			for (int i = rootIndex-1; i >= 0 ; i--) {
				stateArray[i] =  currentState;
				currentState = _bestPointer.get(currentState, i);
			}
			
			return stateArray;
		}

		/**
		 * Finds the index of the maximal element of the col'th column of the sparse matrix doubleMatrix. Only the elements with their index in 
		 * the constraint list are considered.   
		 * 
		 * @param doubleMatrix the matrix.
		 * @param constraint the list of indices to consider.
		 * @param col the column to consider.
		 * @return the index of the maximal element.
		 */
		protected static int argmax(DoubleSparseMatrix doubleMatrix, ArrayList<Integer> constraint, int col) { 
			int argm = 0;
			double max = Double.NEGATIVE_INFINITY;
			for (int k : constraint) {
				double value = doubleMatrix.get(k, col);
				if (value>=max) {
					max = value;
					argm = k; 
				}
			}
			return argm;
		}
		
}
